package me.leetcodepractice;

public class E09Leetcode234 {
    // 判断回文链表
    // 步骤：1.找链表的中间节点，反转后半个链表，然后与后原来的链表逐一比较

    // 1.中间节点
    public ListNode middleNode(ListNode head) {
        ListNode p1 = head;
        ListNode p2 = head;
        // 当p2的下一节点或p2本身为null时，退出循环
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next;
            p2 = p2.next;
        }
        return p1;
    }

    // 2.反转链表
    public ListNode reverse(ListNode o1) {
        ListNode n1 = null; // 新链表
        while (o1 != null) {
            ListNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }

    // 3.判断回文
    public boolean isPalindrome(ListNode head) {
        ListNode middle = middleNode(head);
        ListNode newHead = reverse(middle);
        while (newHead != null) {
            if (newHead.val != head.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 3, 3, 2);
        System.out.println(new E09Leetcode234().isPalindrome(head));
    }
}
